﻿#define _CRT_SECURE_NO_WARNINGS 1
#include<iostream>
using namespace std;
const int N = 1e5 + 10;

int e[N], ne[N], h, id;
int mp[N]; //mp[i]表⽰i在这个元素存放的位置

//头插
void push_front(int x)
{
	//先把x放在⼀个格⼦⾥⾯
	id++;
	e[id] = x;
	mp[x] = id;//标记x存储
	//修改指针，顺序不能颠倒！
	//1.x的右指针指向哨兵位的后继
	//2.哨兵位的右指针指向x
	ne[id] = ne[h];
	ne[h] = id;
}

// 打印链表
void print()
{
	//定义⼀个指针从头结点开始
	//通过ne数组逐渐向后移动
	//直到遇到空指针
	for (int i = ne[h]; i != 0; i = ne[i])
	{
		cout << e[i] << " ";
	}
	cout << endl;
}
//查询值为x的元素存储的位置
int find(int x)// 注意，这⾥传⼊的是元素的值
{
	//策略⼀：先找到x，然后返回x后⾯的元素
	for (int i = ne[h]; i != 0; i = ne[i]) //遍历链表
	{
		if (e[i] == x)return i; // 如果找到x
	}
	//找不到就返回0
	return 0;
	//策略二
	return mp[x];
}
//在存储位置为p的元素后面，插入一个元素x
void insert(int p, int x)// 一定要注意，这里的p是位置，不是元素
{
	id++;//x这个元素分配的位置
	e[id] = x;//将x放在id位置处
	ne[id] = ne[p];//x指向p的后面
	ne[p] = id;//p指向x
}
int main()
{
	for (int i = 1; i <= 5; i++)
	{
		push_front(i);
		print();
	}
	//cout << find(1) << endl;
	//cout << find(2) << endl;
	//cout << find(3) << endl;
	insert(2, 100);
	print();
	return 0;
}
//int h; //头指针
//int id; //下⼀个元素分配的位置
//
//int e[N], ne[N]; //数据域和指针域
////下标0位置作为哨兵位
////其中ne数组全部初始化为0，其中ne[i] = 0就表⽰空指针，后续没有结点
////当然，也可以初始化为-1作为空指针，看个⼈爱好
//
///*
// e[i]和 ne[i]是绑定在⼀起使⽤的，也有⼀种写法是定义⼀个结构体，把这两个变量放在⼀
//起，⽐如：
//
//struct node
//{
// int e, ne;
// }list[N];
//	
//	但是，定义成结构体之后，代码书写不⽅便。我们只要知道e[i]和ne[i]是绑定在⼀起使⽤的即可
//*/